#ifndef _UTILS_DICTIONNARY_H_
#define _UTILS_DICTIONNARY_H_

#include <arduino/WString.h>
#include <utils/memory.h>


namespace utils
{

template <typename _Type>
class dictionnary
{
public:

  dictionnary(void) : _root(nullptr) {}

  ~dictionnary(void) { delete _root; }

  _Type* operator [](String const& str)
  { return _root ? _root->find(str.c_str()) : nullptr; }

  _Type* operator [](char const* str)
  { return _root ? _root->find(str) : nullptr; }

  _Type const* operator [](String const& str) const
  { return _root ? _root->find(str.c_str()) : nullptr; }

  _Type const* operator [](char const* str) const
  { return _root ? _root->find(str) : nullptr; }

  bool insert(String const& str, _Type const& value)
  { return insert(str.c_str(), value); }

  bool insert(char const* str, _Type const& value)
  {
    if (*str == '\0') return false;

    if (_root)
    {
      if (_root->letter > *str)
      {
        element* new_root = new element;
        new_root->next = _root;
        new_root->letter = *str;
        _root = new_root;
      }

      return _root->insert(str, value);
    }

    _root = new element;
    _root->letter = *str;

    element* current = _root;

    while (str[1] != '\0')
    {
      ++str;
      current->follower = new element;
      current = current->follower;
      current->letter = *str;
    }

    current->value = new _Type(value);

    return true;
  }

  void print(int indent = 0)
  { if (_root) _root->print(indent); }

  void print_words(int indent = 0)
  {
    String val = "";
    _root->print_list(indent, val);
  }

private:

  struct element
  {
    element(void)
      : value(nullptr)
      , follower(nullptr)
      , next(nullptr) {}

    ~element(void)
    {
      delete value;
      delete follower;
      delete next;
    }

    void print(int indent)
    {
      for (int i = 0; i < indent; ++i)
        Serial.print("  ");

      Serial.print(letter);

      if (value)
        Serial.println(" -> value");
      else
        Serial.println();

      if (follower) follower->print(indent + 1);
      if (next) next->print(indent);
    }

    void print_list(int indent, String& str)
    {

      if (follower && next)
      {
        String dpl = str;
        next->print_list(indent, dpl);
        str += letter;
        follower->print_list(indent, str);
        return;
      }

      if (follower)
      {
        str += letter;
        follower->print_list(indent, str);
        return;
      }

      if (next)
      {
        next->print_list(indent, str);
        return;
      }

      str += letter;
      Serial.println(str);
    }

    _Type* find(char const* word)
    {
      if (*word < letter)
        return nullptr;

      if (*word == letter)
      {
        if (word[1] == '\0')
          return value;

        return follower->find(++word);
      }

      return next ? next->find(word) : nullptr;
    }

    bool insert(const char* str, _Type const& val)
    {
      if (*str == letter)
      {
        if (str[1] == '\0')
        {
          if (value)
          {
            utils::copy(val, *value);
            return false;
          }
          else
          {
            value = new _Type(val);
            return true;
          }
        }

        if (!follower || follower->letter > str[1])
        {
          element* new_follower = new element;
          new_follower->letter = str[1];
          new_follower->next = follower;
          follower = new_follower;
        }

        return follower->insert(str+1, val);
      }

      if (!next || next->letter > *str)
      {
        element* new_next = new element;
        new_next->next = next;
        new_next->letter = *str;
        next = new_next;
      }

      return next->insert(str, val);
    }

    _Type* value;
    char letter;
    element* follower;
    element* next;
  }* _root;
};

} // utils

#endif // _UTILS_DICTIONNARY_H_
